#include "externalsort.h"

void externalSort(int fdInput, unsigned long size, int fdOutput, unsigned long memSize) 
{
    // how many uin64_ts per split
    unsigned long splitSize = 1L;
    // how many split files we need
    unsigned long splits = 1L;
    
    std::vector<int> fdTmpFiles;
    char* fileNames[splits];
    
    if(size < 1L || memSize < sizeof(uint64_t))
    {
        // nothing to sort
        std::cerr << "No elements to sort or not enough memory to hold uint64_t" << std::endl;
    } else if(size == 1L)
    {
        // write the only entry to result (check if it fits to ram??^^)
    } else
    {
        // determine # of uint64_t's that fit into memSize
        splitSize = memSize/sizeof(uint64_t);
        if(splitSize > size)
        {
            splitSize = size;
        }
        // and how many of those sets
        splits = size/splitSize;
        if(size%splitSize > 0)
        {
            splits++;
        }
        
        std::cout << "memSize: " << memSize << ", size: ";
        std::cout << size << ", sizeof(uint64_t): " << sizeof(uint64_t) << std::endl;
        std::cout << "split size: " << splitSize << ", splits: " << splits << std::endl;

        uint64_t buf;
        int n;
        unsigned long processedItems = 0L;
        unsigned long fileSize = splitSize*sizeof(uint64_t);
        std::vector<uint64_t> splitElements;
        int fileNumber = 0;
        
        int fd, ret;
        // process the input file
        while((n=read(fdInput, &buf, sizeof(uint64_t))) > 0)
        {
            // create filenames for the individual splits that need to be put to disk
            std::stringstream sstm;
            sstm << "tmpSortFile" << fileNumber;
            std::string fileName = sstm.str();
            
            // after a whole split is processed(+ at initialization), write it to disk
            // and create next file
            if(processedItems % splitSize == 0)
            {
                std::stringstream sstm;
                sstm << "tmpSortFile" << fileNumber;
                std::string fileName = sstm.str();
                
                // if a split was populated, sort and write the elements to disk
                if(splitElements.size() > 0)
                {
                    writeSortedToFile(splitElements, fd);
                    // clear split elements
                    splitElements.clear();
                }
                
                // create next file
                if ((fd = open(fileName.c_str(), O_CREAT|O_TRUNC|O_RDWR, S_IRUSR|S_IWUSR)) < 0)
                {
		            std::cerr << "cannot open file '" << fileName << "': " << strerror(errno) << std::endl;
		            return;
	            }
	            
	            // the last split may not be of full size, so only allocate the needed space
	            if(size-processedItems < splitSize){
	                fileSize = (size-processedItems)*sizeof(uint64_t);
                }
	            if ((ret = posix_fallocate(fd, 0, fileSize)) != 0)
		            std::cerr << "warning: could not allocate file space: " << strerror(ret) << std::endl;
		
		        // keep track of filenames
                fileNames[fileNumber] = new char[fileName.size()+1];
                std::copy(fileName.begin(), fileName.end(), fileNames[fileNumber]);
                fileNames[fileNumber][fileName.size()] = '\0';
                // keep track of the file descriptors
                fdTmpFiles.push_back(fd);
                
                fileNumber++;
            }
            splitElements.push_back(buf);
            processedItems++;
        }
        // if the last split was not of full size, there are elements remaining in the vector,
        // write them to the latest file
        if(splitElements.size() > 0)
        {
            writeSortedToFile(splitElements, fd);
            splitElements.clear();
        }
    }
    
    // merge the files
    unsigned int splitFiles = fdTmpFiles.size();
    unsigned int i = 0;
    std::vector<int>::iterator it;
    
    // points to the current element of each split file
    int nextIndex[splitFiles];
    // holds all current elements of the split files
    uint64_t mergeValues[splitFiles];
   
    long elementCount[splitFiles];
    FILE * pFile[splitFiles];
    // initialize the mergeValues array with first items of all lists
    for(i = 0; i < splits; i++)
    {
        pFile[i] = fopen( fileNames[i], "r+" );
        if(pFile[i] != NULL)
        {
            fseek(pFile[i], 0, SEEK_END);
            elementCount[i] = ftell(pFile[i]) / sizeof(uint64_t);
            rewind(pFile[i]);
            int bytesRead = fread(&mergeValues[i], sizeof(uint64_t), 1, pFile[i]);
        }
        nextIndex[i] = 0;
    }
    
    i = 0;
    // size equals the # of items to process
    while( i < size )
    {
        // find minimum item k in mergeValues[]
        // write it to file and advance the next index pointer for that splitfile
        int iMin = minIndex(mergeValues, splitFiles, nextIndex, elementCount);
        // no more valid values found
        if(iMin < 0)
        {
            return;
        }
        
        // write value to disk
        if(write(fdOutput, &mergeValues[iMin], sizeof(uint64_t)) < 0)
        {
            std::cout << "error writing to result file: " << strerror(errno) << std::endl;
        }
        
        nextIndex[iMin]++;
        
        
        // update the value with the next from the file
        if(nextIndex[iMin] < elementCount[iMin])
        {
            mergeValues[iMin] = readOffsetFromFile(pFile[iMin], nextIndex[iMin]);
        }
        
        i++;
    }
    
    // delete the temporary split files
    for(i = 0; i < splits; i++)
    {
        if(remove(fileNames[i]) < 0)
        {
            std::cout << "could not remove temp file: " << strerror(errno) << std::endl;
        }
    }
}

uint64_t readOffsetFromFile(FILE *pFile, int n)
{
    uint64_t result;
    long int offset = n * sizeof(uint64_t);
    fseek(pFile, offset, SEEK_SET);
    int bytesRead = fread(&result, sizeof(uint64_t), 1, pFile);
    rewind(pFile);
    return result;
}

int minIndex(uint64_t values[], int size, int indices[], long elementCount[]) {
    if(size == 0)
    {
        return -1;
    }
    int res = -1;
    
    uint64_t min;
    unsigned int i;
    for(i = 0; i < size; i++)
    {
        if(indices[i] < elementCount[i])
        {
            if(res == -1)
            {
                res = i;
                min = values[i];
            } else {
                if(values[i] < min)
                {
                    min = values[i];
                    res = i;
                }            
            }
        }
    }
    return res;
}

void writeSortedToFile(std::vector<uint64_t> elements, int fdOut)
{
    sort(elements.begin(), elements.end());
    std::vector<uint64_t>::iterator it;
    for(it = elements.begin(); it != elements.end(); ++it)
    {
        uint64_t el = *it;
        if(write(fdOut, &el, sizeof(uint64_t)) < 0)
        {
            std::cerr << "error writing to tmp file: " << strerror(errno) << std::endl;
        }
    }
}
